package 栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/valid-parentheses/
 * @author 86155
 *
 */

public class _20_有效的括号 {
	
	private Map<Character, Character> map = new HashMap<Character, Character>();
	
	public _20_有效的括号() {
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
	}
	
	public boolean isValid2(String s) {
		if (s.length() % 2 != 0) {
            return false;
        }
		Stack<Character> stack = new Stack<Character>();
		for (int i = 0; i < s.length(); i++) {
			char target = s.charAt(i);
			if (map.containsKey(target)) {
				stack.push(target);
			}else {
				if (stack.isEmpty()) {
					return false;
				}
				
				if (target != map.get(stack.pop())) {
					return false;
				}
			}
		}
		return stack.isEmpty();
    }
	
	
	public boolean isValid(String s) {
		if (s.length() % 2 != 0) {
            return false;
        }
		Stack<Character> stack = new Stack<Character>();
		for (int i = 0; i < s.length(); i++) {
			char target = s.charAt(i);
			if (target == '(' || target == '[' || target == '{') {
				stack.push(target);
			}else {
				if (stack.isEmpty()) {
					return false;
				}
				
				char left = stack.pop();
				if (left == '(' && target != ')') {
					return false;
				}
				
				if (left == '[' && target != ']') {
					return false;
				}
				if (left == '{' && target != '}') {
					return false;
				}
			}
		}
		return stack.isEmpty();
    }

}
